package practice1_100;
//接雨水问题
public class Practice42 {
    //暴力算法
    public int trap(int[] height) {
        int len=height.length;
        int sum=0;
        for (int i = 1; i <len-1;i++ ) {
            int l_max=0,r_max=0;
            for (int j=i;j<len;j++){//找出当前的height[i]右边的最大长度
                r_max=Math.max(r_max,height[j]);
            }
            for (int o=i;o>=0;o--){//找出当前的height[i]左边的最大长度
                l_max=Math.max(l_max,height[o]);
            }
            sum=sum+Math.min(l_max,r_max)-height[i];

        }
        return  sum;
    }

    //用备忘录的方式的方式
    public int trap1(int[] height){
        if(height.length==0) return 0;
        int[] l_max=new int[height.length];
        int[] r_max=new int[height.length];
        l_max[0]=height[0];
        r_max[height.length-1]=height[height.length-1];
        int sum=0;
        for (int i=1;i<l_max.length;i++){
            l_max[i]=Math.max(l_max[i-1],height[i]);
        }
        for (int i=r_max.length-2;i>=0;i--){
            r_max[i]=Math.max(r_max[i+1],height[i]);
        }
        for (int i=0;i<height.length;i++){
            sum=sum+Math.min(r_max[i],l_max[i])-height[i];
        }
        return sum;
    }
    public static void main(String[] args) {
        int sum=new Practice42().trap1(new int[] {0,1,0,2,1,0,1,3,2,1,2,1,53,637,8,3,62,63,3,2,6,7,4,96,4,52,5});
        System.out.println(sum);
    }
}
